# This method of level generation is basically purestrain's idea, not mine--
# any innovation is most likely just failed plagiarism. The basic concept is
# that the level is subdivided into suitably-sized rooms by orthogonal
# lines (BSP), and the interior of the generated rectangles are then
# decorated by "room painter" method, such that some rectangles will be
# used for e.g. corridors, instead of traditional rooms.

# Actually, I'm going to deviate from that model and generate corridors
# "traditionally".

# Minimal room:
#
#   #########
#   #...#...#
#   #...#...#
#   #...#...#
#   #########
# 9


# Is it possible that this situation can crop up? I don't want it.
#
# #########            ##########         
# #.......#            #........#        
# #.......#            #........#        
# #.......#            #........#        
# #.......######       #........#          
# ########.....#       #########.########
#        #.....#                #.......#
#        #.....#                #.......#
#        #######                #.......#
#                               #########
#


import random

Padding = 5

class DisconnectedDungeon: pass

class Rectangle:
	def __init__(self, collection, offset, size):
		self.collection = collection
		self.offset = offset
		self.size = size
		self.collection.append( self )
	def split(self):
		span = max( self.size ) - 2*Padding
		if span < 0:
			return False
		choice = random.randint( Padding, Padding + span )

		self.collection.remove( self )

		xLargest = self.size[0] - self.size[1]
		if not xLargest: xLargest = random.choice( [-1,1] )
		x, y = self.offset
		w, h = self.size
		if xLargest > 0:
			Rectangle( self.collection, (x,y), (choice+1,h) )
			Rectangle( self.collection, (x+choice,y), (w-choice,h) )
		else:
			Rectangle( self.collection, (x,y), (w,choice+1) )
			Rectangle( self.collection, (x,y+choice), (w,h-choice) )
		return True
	def area(self):
		return self.size[0] * self.size[1]
	def contains(self, p, excludeCorners = False ):
		x0, y0 = self.offset
		w, h = self.size
		x1, y1 = x0+w-1, y0+h-1
		x, y = p
		if excludeCorners:
			corners = [ (x0+dx,y0+dy) for dx in (0,w-1) for dy in (0,h-1) ]
			if p in corners: return False
		return x >= x0 and x <= x1 and y >= y0 and y <= y1
	def borders(self, rectangle):
		x, y = self.offset
		w, h = self.size
		corners = [ (x+dx,y+dy) for dx in (0,w-1) for dy in (0,h-1) ]
		return max( [ rectangle.contains( corner ) for corner in corners ] )
	def trueNeighbour(self, rectangle):
		x0, y0 = self.offset
		w, h = self.size
		for x in range(x0,x0+w):
			if rectangle.contains( (x,y0), excludeCorners = True ): return True
			if rectangle.contains( (x,y0+h-1), excludeCorners = True ): return True
		for y in range(y0,y0+h):
			if rectangle.contains( (x0,y), excludeCorners = True ): return True
			if rectangle.contains( (x0+w-1,y), excludeCorners = True ): return True
	def neighbours(self, strict = False ):
		if strict:
			return [ rectangle for rectangle in self.collection if rectangle != self and self.trueNeighbour(rectangle) ]
		else:
			return [ rectangle for rectangle in self.collection if rectangle != self and self.borders(rectangle) ]

class Room:
	def __init__(self, shape):
		self.shapes = [ shape ]
		for shape in self.shapes:
			shape.collection.remove( shape )
		self.explored = False
		self.connections = [] # direct
	def explore(self):
		self.explored = True
		for connection in self.connections:
			if not connection.explored:
				connection.explore()
	def connect(self, other):
		if self.explored or other.explored:
			self.explore()
			other.explore()
		self.connections.append( other )
		other.connections.append( self )
	def contains(self, p, excludeCorners = False ):
		return max( [ shape.contains(p, excludeCorners) for shape in self.shapes ] )
	def border(self, p):
		lacks = False
		for dx in (-1,0,1):
			for dy in (-1,0,1):
				x, y = p
				if not self.contains( (x + dx, y + dy) ):
					lacks = True
					break
		return self.contains(p) and lacks
	def neighbours(self, strict = False):
		neighbours = []
		for shape in self.shapes:
			for neighbour in shape.neighbours( strict = strict ):
				if not neighbour in neighbours:
					neighbours.append( neighbour )
		return neighbours
	def pull(self):
		neighbours = self.neighbours( strict=True )
		if not neighbours: return
		neighbour = random.choice( neighbours )
		neighbour.collection.remove( neighbour )
		self.shapes.append( neighbour )
	def paint(self, canvas, brushes):
		for x in range(canvas.width):	
			for y in range(canvas.height):
				if self.contains( (x,y) ):
					if self.border( (x,y) ):
						canvas.tiles[x][y] = brushes.wall.spawn()
					else:
						canvas.tiles[x][y] = brushes.floor.spawn()

class CorridorSpace:
	def __init__(self, rectangle):
		self.rectangle = rectangle
		self.rectangle.collection.remove( rectangle )
	def paint(self, canvas, brushes):
		pass

class LevelGenerator:
	def __init__(self, canvas, brushes):
		self.rectangles = []
		self.rooms = []
		Rectangle( self.rectangles, (0,0), (canvas.width, canvas.height) )
		for i in range(100):
			self.split()
		self.zone()
		self.rooms[0].explored = True
		self.dug = []
		diggable = []
		for x in range( canvas.width ):
			if x == 0 or (x+1) == canvas.width: continue
			for y in range( canvas.height ):
				if y == 0 or (y+1) == canvas.height: continue
				if not max( [ s.contains( (x,y) ) for s in self.rooms ] ):
					diggable.append( (x,y) )
		self.paint( canvas, brushes )
		while self.unexplored():
			self.tryDig( diggable, canvas, brushes )
		for i in range( len( self.rooms ) * 2 ):
			self.tryDig( diggable, canvas, brushes )
		x0, y0 = canvas.getRandomTileOfType( brushes.floor )
		canvas.growDistancesFrom( x0, y0 )
		if None == min( [ canvas.tiles[x][y].pcDist for x in range(canvas.width) for y in range(canvas.height) if canvas.tiles[x][y].type == brushes.floor ] ):
			raise DisconnectedDungeon
	def paint(self, canvas, brushes ):
		for room in self.rooms:
			room.paint( canvas, brushes )
	def roomAt(self, p):
		for room in self.rooms:
			if room.contains(p, excludeCorners=True):
				return room
		return None
	def unexplored(self):
		return bool( [ room for room in self.rooms if not room.explored ] )
	def tryDig(self, diggable, canvas, brushes):
		x0, y0 = random.choice( diggable )
		dir = [ (0,1), (0,-1), (-1,0), (1,0) ]
		diggingDir = [ True ] * 4
		result = [False] * 4
		t = 0
		dug = []
		while max( diggingDir ):
			for i in range(4):
				if not diggingDir[i]: continue
				dx, dy = dir[i]
				x, y = x0 + t * dx, y0 + t * dy
				if not (x,y) in diggable:
					result[i] = self.roomAt( (x,y) )
					diggingDir[i] = False
			t += 1
		endpoints = list(set( [ r for r in result if r != None ] ))
		newConnections = [ (a,b) for a in endpoints for b in endpoints if a != b and not (a in b.connections) ]
		if newConnections:
			for endpoint in endpoints:
				for other in endpoints:
					if endpoint == other: continue
					endpoint.connect( other )
			diggingDir = [ result[i] != None for i in range(4) ]
			t = 0
			while max( diggingDir ):
				for i in range(4):
					if not diggingDir[i]: continue
					dx, dy = dir[i]
					x, y = x0 + t * dx, y0 + t * dy
					if not (x,y) in diggable:
						diggingDir[i] = False
						if random.random() > 0.5:
							canvas.tiles[x][y] = brushes.closedDoor.spawn()
						else:
							canvas.tiles[x][y] = brushes.openDoor.spawn()
					else:
						canvas.tiles[x][y] = brushes.corridor.spawn()
					dug.append( (x,y) )
				t += 1
		for x,y in dug:
			for dx in (-1,0,1):
				for dy in (-1,0,1):
					if (x+dx,y+dy) in diggable:
						diggable.remove( (x+dx,y+dy) )
	def split(self):
		s = 0
		for r in self.rectangles: s += r.area()
		s = random.randint(0, s-1 )
		for r in self.rectangles:
			s -= r.area()
			if s < 0:
				return r.split()
	def makeRoom(self, rectangle ):
		room = Room( rectangle )
		for i in range(3):
			if random.random() > 0.5: room.pull()
		self.rooms.append( room )
		for neighbour in room.neighbours():
			self.rectangles.remove( neighbour )
#			self.rooms.append( CorridorSpace( neighbour ) )
	def zone(self):
		while self.rectangles:
			self.makeRoom( random.choice( self.rectangles ) )
